using System;
using System.Collections.Generic;
using System.Text;
using Calc.Operations;


namespace Calc.Parser
{
	public static class EquationParser
	{
		private enum ParserState
		{
			Math,
			Function,
		}


		public static IOperand Parse(string equation)
		{
			Lexer lexer = new Lexer(equation);

			IOperand ret = Parse(lexer);

			if ( ret == null )
				ret = new Constant(0.0d);

			return ret;
		}

		/// <summary>
		/// This method is recursively called to parse each level of an equation.
		/// </summary>
		/// <param name="lexer"></param>
		/// <returns>The root IOperand that represents with each part of the equation</returns>
		private static IOperand Parse(Lexer lexer)
		{
			if ( lexer == null )
				throw new ArgumentNullException("lexer", "Lexer should never be null");

			LexerToken token = lexer.GetNextToken();

			IOperand root = null;

			IOperand lastOp = null;

			while ( token.TokenType != LexerTokenType.End )
			{
				switch ( token.TokenType )
				{
					case LexerTokenType.Invalid:
						throw new EquationParserException("Invalid token: " + token.Token, token);
					case LexerTokenType.Comma:
						break;
					case LexerTokenType.RightParenthesis:
					case LexerTokenType.End:
						return null;
					case LexerTokenType.LeftParenthesis:
						// check to see if lastOp is a variable
						//
						// if it is, then this is a parameter list 
						// for a either a function declaration or
						// a function call
						if ( lastOp is Variable )
						{
							if ( lastOp is Function)
								throw new EquationParserException("Unexpected ( after function call:" + lastOp.ToString(), token);

							Function function = new Function((Variable)lastOp);

							// change lastOp from a Variable to a function
							IOperator parentOp = FindRightSideOperand(root, lastOp);

							if ( parentOp == null )
							{
								// no parent operation, so just replace root with this
								root = function;
							} 
							else if ( parentOp is BinaryOperator )
							{
								BinaryOperator bpop = (BinaryOperator)parentOp;
								bpop.RightSide = function;
							}
							else if ( parentOp is UnaryOperator )
							{
								UnaryOperator upop = (UnaryOperator)parentOp;
								upop.Operand = function;
							}

							// Why do I feel a strong urge to destroy the Variable here?
							// Garbage collection just feels too lazy
							lastOp = function;

							// recursively call Parse(lexer) to 
							// get each item in the parameter list

							for ( IOperand oper = Parse(lexer); oper != null; oper = Parse(lexer) )
							{
								function.Variables.Add(oper);
							}
						}
						else
						{
							// if not, then its a regular parenthesis
							// and it should be treated as a constant
							// or variable
							IOperand oper = Parse(lexer);
							Parenthesese paren = new Parenthesese(oper);

							// absorb next token
							LexerToken ttoken = lexer.GetNextToken();

							if ( ttoken.TokenType != LexerTokenType.RightParenthesis )
								throw new EquationParserException("Missing closing right parenthesis", ttoken);

							AssignOperand(ref lastOp, ref root, token, paren, "parenthetic equation");
						}
						break;
					case LexerTokenType.Constant:
						Constant con = CreateConstant(token);

						AssignOperand(ref lastOp, ref root, token, con, "constant");
						break;
					case LexerTokenType.String:
						Variable var = CreateVariable(token);

						AssignOperand(ref lastOp, ref root, token, var, "variable");
						break;
					case LexerTokenType.Operator:
						IOperator op = CreateOperator(token);

						// check for two operators in a row
						if ( lastOp != null && lastOp is BinaryOperator )
						{
							BinaryOperator bLOp = (BinaryOperator)lastOp;
							if ( bLOp.RightSide == null )
								throw new EquationParserException("Can not have two operators in a row.", token);
						}

						if ( root is BinaryOperator )
						{
							BinaryOperator bRoot = (BinaryOperator)root;

							BinaryOperator npOp = FindNewParentOp(bRoot, op);

							if ( npOp == null )
							{
								if ( !( op is BinaryOperator ) )
									throw new EquationParserException(
										"A unary operator was found with precedence that is too low for some reason", token);

								// should never happen with anything thats not a binary operator
								BinaryOperator bop = (BinaryOperator)op;
								bop.LeftSide = root;

								root = bop;

								lastOp = bop;
							}
							else
							{
								// we have an object in the equation with lower precedence than
								// this operator, so we take the new parent ops (the farthest down
								// object with lower precedence), make its left side our right side,
								// and then make this operation its left side

								if ( op is BinaryOperator )
								{
									BinaryOperator bop = (BinaryOperator)op;

									bop.LeftSide = npOp.RightSide;

									npOp.RightSide = bop;

								}
								else if ( op is UnaryOperator )
								{
									UnaryOperator uop = (UnaryOperator)op;
									uop.Operand = npOp.RightSide;

									npOp.RightSide = uop;
								}

								lastOp = op;
							}
						}
						else if ( root != null )
						{
							if ( root is Constant || root is Variable || root is Parenthesese )
							{
								if ( op is BinaryOperator )
								{
									BinaryOperator bop = (BinaryOperator)op;
									bop.LeftSide = root;

									lastOp = bop;
									root = bop;
								}
								else if ( op is UnaryOperator )
								{
									UnaryOperator uop = (UnaryOperator)op;
									uop.Operand = root;

									lastOp = uop;
									root = uop;
								}
							}
						}
						else if ( root == null )
						{
							throw new EquationParserException("Unexpected operator in statement", token);
						}

						break;
				}

				// look for closure tokens
				LexerToken peek = lexer.PeekNextToken();

				if ( peek.TokenType == LexerTokenType.Comma || peek.TokenType == LexerTokenType.RightParenthesis || peek.TokenType == LexerTokenType.End )
				{
					//lexer.GetNextToken();
					return root;
				}

				token = lexer.GetNextToken();

			}

			return root;
		}

		private static void AssignOperand(ref IOperand lastOp, ref IOperand root, LexerToken token, IOperand oper, string type)
		{
			if ( lastOp != null )
			{
				if ( lastOp is BinaryOperator )
				{
					BinaryOperator blop = (BinaryOperator)lastOp;

					if ( blop.RightSide != null )
					{
						// two constants/variables in a row
						// not good
						throw new EquationParserException("Unexpected " + type, token);
					}

					blop.RightSide = oper;

					lastOp = oper;
				}
				else if ( lastOp is UnaryOperator )
				{
					// incorrect state - unary operators are preceded by their operands,
					// so they should only be followed by other operators
					throw new EquationParserException("Unexpected " + type + " after unary operator", token);
				}
			}
			else
			{
				if ( root == null )
					root = oper;
				lastOp = oper;
			}
		}

		private static Variable CreateVariable(LexerToken token)
		{
			Variable var = new Variable(token.Token);

			return var;
		}

		private static Constant CreateConstant(LexerToken token)
		{
			double val;

			if ( !double.TryParse(token.Token, out val) )
			{
				val = 0.0d;
			}

			return new Constant(val);
		}

		private static IOperator CreateOperator(LexerToken token)
		{
			IOperator op = null;
			switch ( token.Token )
			{
				case "+":
					op = new AddOperator();
					break;
				case "-":
					op = new SubtractOperator();
					break;
				case "*":
					op = new MultiplyOperator();
					break;
				case "/":
					op = new DivideOperator();
					break;
				case "%":
					op = new ModuloOperator();
					break;
				case "=":
					op = new AssignmentOperator();
					break;
			}

			return op;
		}

		/// <summary>
		/// Recursively searches the RightSide (or only) nodes or root to find the
		/// the operator that has IOperand as its operand
		/// </summary>
		/// <param name="root">The current object to check</param>
		/// <param name="find"></param>
		/// <returns></returns>
		private static IOperator FindRightSideOperand(IOperand root, IOperand find)
		{
			if ( root == null )
				return null;

			if ( root is BinaryOperator )
			{
				BinaryOperator bop = (BinaryOperator)root;
				if ( bop.RightSide == find )
					return bop;
				else
					return FindRightSideOperand(bop.RightSide, find);
			}
			else if ( root is UnaryOperator )
			{
				UnaryOperator uop = (UnaryOperator)root;
				if ( uop.Operand == find )
					return uop;
				else
					return FindRightSideOperand(uop.Operand, find);
			}

			return null;
		}

		private static BinaryOperator FindNewParentOp(BinaryOperator root, IOperator current)
		{
			BinaryOperator level = root as BinaryOperator;
			BinaryOperator prevLevel = null;

			while ( level != null )
			{
				if ( level.Precidence < current.Precidence )
				{
					if ( level.RightSide is BinaryOperator )
					{
						prevLevel = level;
						level = (BinaryOperator)level.RightSide;
					}
					else
					{
						return level;
					}
				}
				else
				{
					return prevLevel;
				}
			}

			return null;
		}
	}
}
